package com.heima.leetcode.practice;

import java.util.HashSet;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 128. 最长连续序列
 * @date 2025/1/15 21:03
 */
public class E128 {

    /**
     * 存放数字，HashSet或者HashMap可以去重
     */
    private final HashSet<Integer> set = new HashSet<>();

    /**
     * <h3>方法一：用hashset</h3>
     * @param nums nums数组
     * @return 最长连续序列的长度
     */
    public int longestConsecutive(int[] nums) {
        // 1. 遍历数组，将数组中的元素添加到 HashSet 中。
        for (int num : nums) set.add(num);
        int maxLength = 0, length = 1;
        // 2. 遍历 HashSet 中的元素，因为HashSet中的元素是去重了的，效率快很多。
        for (int num : set) {
            // 2.1 判断当前元素是否是连续序列的第一个元素，如果是，则开始计算连续序列的长度。
            // 这样的话就不是对每个元素都要找其开始的连续序列了，而是只会对每个连续序列的第一个元素进行查找。
            if (!set.contains(num - 1)){
                while (set.contains(++num)) length++;
                maxLength = Math.max(maxLength, length);
                length = 1;
            }
        }
        // 3. 返回最长连续序列的长度。
        return maxLength;
    }
}
